home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 003 / db3_hdr.doc < prev    next >
Text File  |  1987-02-24  |  4KB  |  88 lines
  1.                      .DBF and .NDX Header Definitions
  2.  
  3. Compiled by Curtis H. Hoffmann, 02/20/87.   
  4. If you find any errors or omissions, let me know on Terraboard (612)-721-8967.
  5.  
  6.  
  7.    .DBF Primary Header
  8.    -------------------
  9. Address     Contents       Description
  10. -------     --------       -----------
  11.     0       1 byte         Database type: 03 if data; 83 if there is an
  12.                            associated memo file
  13.   1-3       3 ASCII char.  Date last updated, in YY,MM,DD format
  14.   4-7       32 bit #       Number of records in file
  15.   8-9       16 bit #       Starting location of data
  16.  10-11      16 bit #       Length of records (total field size +1)
  17.  12-31      20 bytes       (Reserved)
  18.  32-n       32 bytes ea.   Field descripter array
  19.   n+1       1 byte         0D hex terminator
  20.  
  21.    .DBF Field Descripter Array
  22.    ---------------------------
  23.      0      1 byte         Deletion marker; 2A if marked else 20 hex
  24.   1-10      10 bytes       Field name in ASCII (0 as terminator)
  25.     11      1 byte         Field type in ASCII
  26.  12-15      32 bit #       Field data address (internal use)
  27.     16      1 byte         Field length in binary
  28.     17      1 byte         Field decimal count in binary
  29.  18-31      14 bytes       (reserved)
  30.  
  31. =======================================================================
  32.  
  33.    .NDX Anchor Node Heading
  34.    ------------------------
  35. Address   Contents    Description
  36. -------   --------    -----------
  37.   0-1     2 bytes     (Reserved)
  38.   4-5     16 bit #    Node number of root node
  39.   8-9     16 bit #    Node number of next available node
  40.    12     1 byte      Length of key in binary
  41.    14     1 byte      Maximum number of keys per 512 byte node
  42.    16     1 byte      Index key type; 0 if character key, else 01
  43.    18     1 byte      length of key records in binary (includes address
  44.                       to .DBF file)
  45.  24-279   256 bytes   Key expression in ASCII (00 hex as terminator)
  46. 280-511   232 bytes   (Unused)
  47.  
  48.    .NDX Array (all other nodes)
  49.    ----------------------------
  50.  
  51.      0     1 byte          Number of records in this node
  52.    4-7     32 bit #        Identifies type of node; 0 if a leaf else the node 
  53.                            number of the next branch of the tree
  54.    8-11    32 bit #        If not a branch then this is the address to the
  55.                            corresponding .DBF record
  56.   12-n     mod 8 bytes     Key expression
  57.   n+1-512  record length   Repeating addresses and key expressions until the
  58.                            end of the node
  59.    
  60.    Every node is 512 bytes long, treated as part of a B+ tree.  If the node
  61. is a branch, then compare the match pattern with the key expression.  If the
  62. pattern <= the key, then go to the appropriate lower lever node, otherwise 
  63. go to the next key in that node.  Do this only for the number of keys in this
  64. node.
  65.  
  66.  
  67. Algorithm for finding a given record:
  68. -------------------------------------
  69.  
  70. A)  Read starting node # (SN), length of key (LOK), length of key 
  71.     record (LOKR), and total number of nodes (TON).
  72. B)  Goto starting node (SN*512).  Check to see if the node is a leaf or a
  73.     branch (addresses 4 through 7 = 0 if leaf).  Current node (CN) = SN
  74. C)  Get number of records for this node (NOR).  Zero pointer.  <--
  75. D)  While current node < TON and desired record not found, do:   |
  76.        While pointer <= NOR and record not found, do:            |
  77.           piece key expression together.                         |
  78.           cs=512*CN+12+(pointer-1)*LOKR.                         |
  79.           if match pattern <= key expression, do:                |
  80.              if branch then CN=contents at cs+4.  Repeat ---------
  81.              if not branch and match pattern=key then, do:       |
  82.                 data field record at cs+8.                       |
  83.                 ** Done **                                       |
  84.           else increment pointer                                 |
  85.        If end of node and match not made, do:                    |
  86.           If branch, current node = contents of cs+4.  Repeat ----
  87.           If not branch, then record not in index.  ** Done **
  88.